#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
using namespace std;

class Node {
public:
    int val;
    Node* left;
    Node* right;

    Node() {}

    Node(int _val) {
        val = _val;
        left = NULL;
        right = NULL;
    }

    Node(int _val, Node* _left, Node* _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        return qsort(nums, 0, nums.size() - 1, k);
    }

    int qsort(vector<int>& nums, int l, int r, int k)
    {
        if (l == r) return nums[l];
        int key = getnum(nums, l, r);
        int left = l - 1, right = r + 1, i = l;
        while (i < right)
        {
            if (nums[i] < key) swap(nums[++left], nums[i++]);
            else if (nums[i] == key) ++i;
            else swap(nums[--right], nums[i]);
        }

        int c = r - right + 1, b = right - left - 1;
        if (c >= k) return qsort(nums, right, r, k);
        else if (b + c >= k) return key;
        else return qsort(nums, l, left, k - b - c);
    }

    int getnum(vector<int>& nums, int l, int r)
    {
        return nums[rand() % (r - l + 1) + l];
    }

    vector<int> smallestK(vector<int>& arr, int k) {
        qsort(arr, 0, arr.size() - 1, k);
        return { arr.begin(),arr.begin() + k };
    }
    void _qsort(vector<int>& arr, int l, int r, int k)
    {
        if (l >= r) return;
        int key = getnum(arr, l, r);
        int left = l - 1, right = r + 1, i = l;
        while (i < right)
        {
            if (arr[i] < key) swap(arr[++left], arr[i++]);
            else if (arr[i] == key) ++i;
            else swap(arr[--right], arr[i]);
        }
        int a = left - l + 1, b = right - left - 1;
        if (a > k) qsort(arr, l, left, k);
        else if (a + b >= k) return;
        else qsort(arr, right, r, k - a - b);
    }
    int _getnum(vector<int>& arr, int left, int right)
    {
        return arr[rand() % (right - left + 1) + left];
    }

    void treeconvert(Node* cur, Node*& prev)
    {
        if (cur == nullptr) return;
        treeconvert(cur->left, prev);
        cur->left = prev;
        if (prev) prev->right = cur;
        prev = cur;
        treeconvert(cur->right, prev);
    }

    Node* treeToDoublyList(Node* root) {
        if (root == nullptr) return nullptr;
        Node* prev = nullptr;
        treeconvert(root, prev);

        Node* head = root;
        while (head->left)
            head = head->left;
        prev->right = head;
        head->left = prev;
        return head;
    }

    TreeNode* tree(vector<int>& preorder, vector<int>& inorder, int& prei, int inbegin, int inend)
    {
        if (inbegin > inend) return nullptr;
        TreeNode* root = new TreeNode(preorder[prei]);

        int rooti = inbegin;
        while (rooti <= inend)
        {
            if (inorder[rooti] == preorder[prei]) break;
            else ++rooti;
        }
        ++prei;
        root->left = tree(preorder, inorder, prei, inbegin, rooti - 1);
        root->right = tree(preorder, inorder, prei, rooti + 1, inend);
        return root;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int i = 0;
        return tree(preorder, inorder, i, 0, inorder.size() - 1);
    }

    TreeNode* _tree(vector<int>& postorder, vector<int>& inorder, int& posti, int inbegin, int inend)
    {
        if (inbegin > inend) return nullptr;
        TreeNode* root = new TreeNode(postorder[posti]);

        int rooti = inbegin;
        while (rooti <= inend)
        {
            if (inorder[rooti] == postorder[posti]) break;
            else ++rooti;
        }
        --posti;
        root->right = tree(postorder, inorder, posti, rooti + 1, inend);
        root->left = tree(postorder, inorder, posti, inbegin, rooti - 1);

        return root;
    }

    TreeNode* _buildTree(vector<int>& inorder, vector<int>& postorder) {
        int i = postorder.size() - 1;
        return tree(postorder, inorder, i, 0, inorder.size() - 1);
    }
};